package org.aplombh.java.interview.newcoder;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class HJ44_Sudoku {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[][] sudo = new int[10][10];
        for (int i = 1; i < 10; i++) {
            for (int j = 1; j < 10; j++) {
                sudo[i][j] = in.nextInt();
                int digit = sudo[i][j];
                if (sudo[i][j] == 0) {
                    spaces.add(new Pair(i, j));
                } else {
                    line[i][digit] = column[j][digit] = block[((i - 1) / 3) * 3 + (j - 1) / 3][digit] = true;
                }
            }
        }
        dfs(sudo, 0);
        for (int i = 1; i < 10; i++) {
            for (int j = 1; j < 10; j++) {
                System.out.print(sudo[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static final boolean[][] line = new boolean[10][10];
    private static final boolean[][] column = new boolean[10][10];
    private static final boolean[][] block = new boolean[10][10];

    private static boolean valid = false;
    private static final List<Pair> spaces = new ArrayList<>();

    public static void dfs(int[][] sudo, int idx) {
        if (idx == spaces.size()) {
            valid = true;
            return;
        }

        Pair space = spaces.get(idx);

        int i = space.l, j = space.r;

        // 从0开始依次尝试赋值
        for (int digit = 1; digit < 10 && !valid; digit++) {
            // 判断当前位置是否合法
            if (!line[i][digit] && !column[j][digit] && !block[((i - 1) / 3) * 3 + (j - 1) / 3][digit]) {
                // 赋值
                line[i][digit] = column[j][digit] = block[((i - 1) / 3) * 3 + (j - 1) / 3][digit] = true;
                sudo[i][j] = digit;
                // 递归
                dfs(sudo, idx + 1);
                // 回溯
                line[i][digit] = column[j][digit] = block[((i - 1) / 3) * 3 + (j - 1) / 3][digit] = false;
            }
        }
    }
}

class Pair {
    public int l;
    public int r;

    public Pair(int l, int r) {
        this.l = l;
        this.r = r;
    }
}